翻訳と辞書 Words near each other ・ Rational quadratic covariance function ・ Rational Quality Manager ・ Rational R1000 ・ Rational reciprocity law ・ Rational reconstruction ・ Rational reconstruction (mathematics) ・ Rational Recovery ・ Rational representation ・ Rational Response Squad ・ Rational Rhapsody ・ Rational root theorem ・ Rational sequence topology ・ Rational series ・ Rational Service Tester for SOA Quality ・ Rational set ・ Rational sieve ・ Rational singularity ・ Rational Software ・ Rational Software Architect ・ Rational Software Modeler ・ Rational solution for Collaborative Lifecycle Management ・ Rational surface ・ Rational Synergy ・ Rational Tau ・ Rational Team Concert ・ Rational temperament ・ Rational trigonometry ・ Rational Unified Process ・ Rational variety ・ Rational Youth Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Rational sieve ： ウィキペディア英語版 Rational sieve In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is essentially a special case of the general number field sieve, and while it is far less efficient than the general algorithm, it is conceptually far simpler. So while it is rather useless as a practical factoring algorithm, it is a helpful first step for those trying to understand how the general number field sieve works. == Method == Suppose we are trying to factor the composite number ''n''. We choose a bound ''B'', and identify the ''factor base'' (which we will call ''P''), the set of all primes less than or equal to ''B''. Next, we search for positive integers ''z'' such that both ''z'' and ''z+n'' are ''B''-smooth — i.e. all of their prime factors are in ''P''. We can therefore write, for suitable exponents $a\_k$, $z=\backslash prod\_\; p\_i^$ and likewise, for suitable $b\_k$, we have $z+n=\backslash prod\_\; p\_i^$. But $z$ and $z+n$ are congruent modulo $n$, and so each such integer ''z'' that we find yields a multiplicative relation (mod ''n'') among the elements of ''P'', i.e. :$\backslash prod\_\; p\_i^\; \backslash equiv\; \backslash prod\_\; p\_i^\; \backslash ;\; \backslash operatorname\; \backslash ;\; n\; \backslash operatorname$ (where the ''ai'' and ''bi'' are nonnegative integers.) When we have generated enough of these relations (it's generally sufficient that the number of relations be a few more than the size of ''P''), we can use the methods of linear algebra to multiply together these various relations in such a way that the exponents of the primes are all even. This will give us a congruence of squares of the form a2≡b2 (mod ''n''), which can be turned into a factorization of ''n'', ''n'' = gcd(''a''-''b'',''n'')×gcd(''a''+''b'',''n''). This factorization might turn out to be trivial (i.e. ''n''=''n''×1), in which case we have to try again with a different combination of relations; but with luck we will get a nontrivial pair of factors of ''n'', and the algorithm will terminate. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rational sieve」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.